#include <bits/stdc++.h>

using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3f;

void solve()
{
    int n, t;
    cin >> n >> t;
    string s;
    cin >> s;
    vector<int> a;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            if (cnt)
            {
                a.push_back(cnt);
                cnt = 0;
            }
        }
        else cnt++;
    }
    if (cnt) a.push_back(cnt);
    if (!a.size())
    {
        cout << 0 << endl;
        return;
    }
    if (s[0] != '1' && s.back() != '1')
    {
        a[0] += a.back();
        a.pop_back();
    }
    int ans = 0;
    sort(a.begin(), a.end());
    int ma = a.back();
    for (auto e : a)
    {
        if (e - 2 * t > 0)
            ans += e - 2 * t;
        //ans = max(ans, e-t-1);
    }
    if (ma - t - 1 > 0 && ma - 2 * t > 0 && ma - t - 1 > ma - 2 * t) ans += t - 1;
    else if (ma - t - 1 > 0 && ma - t - 1 > ma - 2 * t) ans += ma - t - 1;
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}